package qsc.algorithm.pack;

/**
 * @auther QiuShangcheng
 * @create 2021/5/1
 */
public class ReStudy {
    public static void main(String[] args) {
        int[] weight = {1,4,3};
        int[] val = {1500,3000,2000};
        ReStudy.pack01(4, 3, weight, val);
    }

    public static void pack01(int V, int N, int[] weight, int[] value) {
        int[][] dp = new int[N + 1][V + 1];
        for (int i = 1; i < N + 1; i++) {
            for (int j = 1; j < V + 1; j++) {
                if (weight[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }

            }
        }
        int j = V;
        String num = "";
        for (int i = N; i > 0; i--) {
            if (dp[i][j]>dp[i-1][j]){
                num = i+" "+num;
                j=j-weight[i-1];
            }
            if (j==0) break;
        }

        System.out.println(num);
        System.out.println(dp[N][V]);
    }

}
